<!DOCTYPE HTML>
<html lang="zh-CN">


<head>
    <meta charset="utf-8">
    <meta name="keywords" content="锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量, python,machine learning,deep learning,html,css,c,c++,cpp,cmake,ros,linux,ubuntu">
    <meta name="description" content="本文介绍了各种锁：自旋锁、互斥锁、条件锁、信号量及其实现">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="referrer" content="no-referrer-when-downgrade">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量 | JackWang&#39;s Blog</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/all.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">

    <script src="/libs/jquery/jquery-3.6.0.min.js"></script>

<meta name="generator" content="Hexo 5.4.2">
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; }  .github-emoji > span { position: relative; z-index: 10; }  .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; }  .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>



   <style>
    body{
       background-image: url(https://cdn.jsdelivr.net/gh/Tokisaki-Galaxy/res/site/medias/background.jpg);
       background-repeat:no-repeat;
       background-size: 100% 100%;
       background-attachment:fixed;
    }
</style>



<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">JackWang&#39;s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="" class="waves-effect waves-light">

      
      <i class="fas fa-book-reader" style="zoom: 0.6;"></i>
      
      <span>博客</span>
      <i class="fas fa-chevron-down" aria-hidden="true" style="zoom: 0.6;"></i>
    </a>
    <ul class="sub-nav menus_item_child ">
      
      <li>
        <a href="/tags">
          
          <i class="fas fa-tags" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按标签归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/categories">
          
          <i class="fas fa-bookmark" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按目录归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/archives">
          
          <i class="fas fa-archive" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按日期分类文章</span>
        </a>
      </li>
      
    </ul>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>



<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">JackWang&#39;s Blog</div>
        <div class="logo-desc">
            
            JackWang的个人博客
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="javascript:;">
			
				<i class="fa-fw fas fa-book-reader"></i>
			
			博客
			<span class="m-icon"><i class="fas fa-chevron-right"></i></span>
		</a>
            <ul  style="background:  ;" >
              
                <li>

                  <a href="/tags " style="margin-left:75px">
				  
				   <i class="fa fas fa-tags" style="position: absolute;left:50px" ></i>
			      
                              <span>按标签归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/categories " style="margin-left:75px">
				  
				   <i class="fa fas fa-bookmark" style="position: absolute;left:50px" ></i>
			      
                              <span>按目录归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/archives " style="margin-left:75px">
				  
				   <i class="fa fas fa-archive" style="position: absolute;left:50px" ></i>
			      
                              <span>按日期分类文章</    span>

                  </a>
                </li>
              
            </ul>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('抱歉，这篇文章并不想让所有人都看到，请输入授权密码观看')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221113224353603.png')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/Operating-System/">
                                <span class="chip bg-color">Operating System</span>
                            </a>
                        
                            <a href="/tags/%E9%94%81/">
                                <span class="chip bg-color">锁</span>
                            </a>
                        
                            <a href="/tags/%E4%BF%A1%E5%8F%B7%E9%87%8F/">
                                <span class="chip bg-color">信号量</span>
                            </a>
                        
                            <a href="/tags/%E4%BA%92%E6%96%A5%E9%94%81/">
                                <span class="chip bg-color">互斥锁</span>
                            </a>
                        
                            <a href="/tags/%E8%87%AA%E6%97%8B%E9%94%81/">
                                <span class="chip bg-color">自旋锁</span>
                            </a>
                        
                            <a href="/tags/%E6%9D%A1%E4%BB%B6%E9%94%81/">
                                <span class="chip bg-color">条件锁</span>
                            </a>
                        
                            <a href="/tags/%E6%9D%A1%E4%BB%B6%E5%8F%98%E9%87%8F/">
                                <span class="chip bg-color">条件变量</span>
                            </a>
                        
                            <a href="/tags/%E9%94%81%E7%9A%84%E5%AE%9E%E7%8E%B0/">
                                <span class="chip bg-color">锁的实现</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                操作系统
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2022-11-13
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>更新日期:&nbsp;&nbsp;
                    2023-06-01
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>文章字数:&nbsp;&nbsp;
                    8.8k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    33 分
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221113224353603.png" alt="锁"></p>
<h1 id="锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量"><a href="#锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量" class="headerlink" title="锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量"></a>锁及其实现：自旋锁、互斥锁、条件锁（条件变量）以及信号量</h1><blockquote>
<p>高性能编程中，锁是真的有用</p>
</blockquote>
<p>锁这个东西，学的时候是真的学明白了。但是用的时候，却又忘了，所以特地写一篇文章记录一下。</p>
<h2 id="一、锁的介绍：以互斥锁为例"><a href="#一、锁的介绍：以互斥锁为例" class="headerlink" title="一、锁的介绍：以互斥锁为例"></a>一、锁的介绍：以互斥锁为例</h2><p>我们首先先介绍为什么要有锁，而后介绍锁的意义。</p>
<h3 id="1-共享数据问题：数据不一致"><a href="#1-共享数据问题：数据不一致" class="headerlink" title="1. 共享数据问题：数据不一致"></a>1. 共享数据问题：数据不一致</h3><p>说到为什么我们需要锁，这就不得不说并行编程了。而说到并行编程，最常见的就是多线程场景。</p>
<p>我们先看看下面的这个多线程程序：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;stdio.h></span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;pthread.h></span></span>
<span class="token comment" spellcheck="true">// #include "common.h"</span>
<span class="token comment" spellcheck="true">// #include "common_threads.h"</span>


<span class="token keyword">static</span> <span class="token keyword">volatile</span> <span class="token keyword">int</span> counter <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token comment" spellcheck="true">// mythread()</span>
<span class="token comment" spellcheck="true">//</span>
<span class="token comment" spellcheck="true">// Simply adds 1 to counter repeatedly, in a loop</span>
<span class="token comment" spellcheck="true">// No, this is not how you would add 10,000,000 to</span>
<span class="token comment" spellcheck="true">// a counter, but it shows the problem nicely.</span>
<span class="token comment" spellcheck="true">//</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">mythread</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s: begin\n"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> i<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">1e7</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        counter <span class="token operator">=</span> counter <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s: done\n"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment" spellcheck="true">// main()</span>
<span class="token comment" spellcheck="true">//</span>
<span class="token comment" spellcheck="true">// Just launches two threads (pthread_create)</span>
<span class="token comment" spellcheck="true">// and then waits for them (pthread_join)</span>
<span class="token comment" spellcheck="true">//</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    pthread_t p1<span class="token punctuation">,</span> p2<span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"main: begin (counter = %d)\n"</span><span class="token punctuation">,</span> counter<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>p1<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> mythread<span class="token punctuation">,</span> <span class="token string">"A"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>p2<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> mythread<span class="token punctuation">,</span> <span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// join waits for the threads to finish</span>
    <span class="token function">pthread_join</span><span class="token punctuation">(</span>p1<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_join</span><span class="token punctuation">(</span>p2<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"main: done with both (counter = %d)\n"</span><span class="token punctuation">,</span> counter<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>程序本身比较简单，就是启动两个线程去增加全局变量<code>counter</code>。这里的含义就是假设每次进行加法计算都特别耗时（真实环境下可能是诸如查询数据库等等功能），我们希望能够更快进行计算（相同时间处理更多的数据库查询），所以启动了两个线程。</p>
<p>我们这里最终希望程序能够更快的把<code>counter</code>加到<code>2e7</code>，我们运行这个程序来看看结果。</p>
<pre class="line-numbers language-bash"><code class="language-bash">./bin/problem
./bin/problem
./bin/problem
./bin/problem
./bin/problem
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>运行结果如下：</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221113232258316.png" alt="运行结果"></p>
<p>我们发现，没有一次的计算结果是<code>2e7</code>。哪怕我们是把加法换成了减法，问题还是一样存在的，几乎没有一次能计算对。而导致这一问题的罪魁祸首，就是因为我们在多个线程中共享了<code>counter</code>这个变量。如果两个线程各自对一个变量，例如各自对<code>counter_A</code>和<code>counter_B</code>进行计算，那么各自的结果都是对的，最终的结果都是<code>1e7</code>。但是一旦我们让两个线程共享同一个变量，那么就会存在问题。</p>
<p>所以这就是多线程编程，或者说并行编程中最大的问题：共享数据存在问题。<strong>共享数据问题有很多种，这里的问题就是数据不一致问题</strong>。</p>
<h3 id="2-数据不一致问题：不可控的调度"><a href="#2-数据不一致问题：不可控的调度" class="headerlink" title="2. 数据不一致问题：不可控的调度"></a>2. 数据不一致问题：不可控的调度</h3><p>为了能够让多线程编程按照我们希望的方式运行，我们就需要解决共享变量问题。而为了解决这一问题，我们需要先明白上述问题的根本原因是什么。</p>
<p>在我们看来，加法就是加法，加法计算就是一步的事情，为什么两个线程的<code>2e7</code>次加法中有将近<code>1e7</code>次加法没加上呢？例如在我们的眼中，下述加法就是一步的事情：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// int a = 0;</span>
a <span class="token operator">=</span> a <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<p>可是在记起来看，上述加法其实是三步（假设变量<code>a</code>存储在<code>0x8049a1c</code>这个内存地址中）：</p>
<pre class="line-numbers language-assembly"><code class="language-assembly">mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>所以只有当<code>mov %eax, 0x8049a1c</code>这个语句运行完了之后，加法才算是计算完了。而如果某个线程才运行到第二步，即<code>add $0x1, $eax</code>的时候，该线程因为<code>CPU</code>调度或者中断等等原因，导致被其他的线程在使用<code>CPU</code>。</p>
<p>而因为我们只运行到第二个指令，而没有保存<code>eax</code>寄存器的值，<code>eax</code>寄存器中暂存的值，又被正在运行的线程覆盖掉了，那么这个时候就相当于少了以此计算。</p>
<p>因此导致共享变量问题的根本原因，其实就是因为我们没有办法在程序中去控制什么时候发生调度。</p>
<h3 id="3-解决办法：原子操作（Atomic-Operation）"><a href="#3-解决办法：原子操作（Atomic-Operation）" class="headerlink" title="3. 解决办法：原子操作（Atomic Operation）"></a>3. 解决办法：原子操作（Atomic Operation）</h3><p>导致共享数据问题发生的元凶就是因为不可控的调度。而为了解决共享数据问题，我们其实有两种思路：</p>
<ul>
<li><strong>思路一：程序决定在完成加法的三条指令后再被调度</strong></li>
<li><strong>思路二：让三条加法指令称为一条指令，三条指令运行期间不会被调度</strong></li>
</ul>
<p>思路一可以解决问题，但是不太可能实现。因为操作调度器这个应该是内核来完成的，我们写的用户程序，是没有权限去操作调度器的。因此，唯一可能得解决方法就是思路二。</p>
<p>高级语言会被翻译成机器指令，而一个机器指令对应着具体得硬件电路的实现，因此我们通过设计电路，是可以实现让上面的三条指令有一个电路实现，即由一个电路（一条指令）完成：从内存中获取值、计算值、将值写回内存中这三件事。而不需要分别用三个电路（三个指令）实现。</p>
<p><strong>思路二的核心，就是希望一些关键的代码不会被进程调度所打断，他们能够一口气执行完，而后再被调度</strong>。只不过思路二是以硬件的方式去实现不会被进程调度打断，其实还有软件的实现方式，不过为了简单、好理解这里就将硬件的解法。</p>
<p>而<strong>这种不会被线程调度机制打断的操作，称为<code>原子操作（Atomic Operation）</code></strong>。所以，解决共享变量问题的核心，就是让加法变成原子加法。</p>
<h3 id="4-原子操作的替换：锁机制（Lock）"><a href="#4-原子操作的替换：锁机制（Lock）" class="headerlink" title="4. 原子操作的替换：锁机制（Lock）"></a>4. 原子操作的替换：锁机制（Lock）</h3><p>把一些<strong>简单的操作</strong>，例如加法变成原子加法，确实能够解决多线程下的共享数据问题。但是<strong>很多时候我们都希望能够具有原子性的操作，由于太复杂了，是没有办法变成原子性的</strong>，例如写文件这个操作，加入要写入1个G的数据，那么因为是原子性的写文件，写入文件的程序无法被调度，则此时在用户的角度看来，计算机仿佛卡死了一样，体验非常不好。而且，这样做还会造成安全问题，程序只要间隔一段时间去读写一次文件，就能够避开调度，从而实现永久的使用<code>CPU</code>。</p>
<p><strong>因此，为了能够让一些复杂的操作实现原子性，就出现了<code>锁（Lock）</code>机制</strong>。</p>
<p><strong>锁这个机制的根本含义就是，在当前修改全局变量之前先看看有没有别的线程正在修改这个变量，如果有的话就等待其他线程修改完毕，而后再修改当前变量</strong>。程序的描述如下：</p>
<pre class="line-numbers language-c"><code class="language-c">lock_t mutex<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// some globally-allocated lock ’mutex’</span>
<span class="token keyword">int</span> balance <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>

<span class="token keyword">int</span> <span class="token function">thread_A</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    <span class="token function">lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    balance <span class="token operator">=</span> balance <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token function">unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>首先需要说明的是，锁本身就是一个变量，即上面的<code>mutex</code>变量。而之所以将锁命名为<code>mutex</code>，其实就是取了英文互斥：<code>Mutual Exclusion</code>的缩写。稍后我们介绍锁实现的功能其实就是保证了程序对共享变量的互斥修改，因此将锁的变量名称为<code>mutex</code>。</p>
<p>话说回来，锁是一个变量（C语言的实现中就是一个<code>struct</code>），因此其内部是能够保存一些状态的。而这些状态一般不是给我们成员用的，而是给对锁有两个操作：<code>lock</code>和<code>unlock</code>操作使用的。而关于这两个操作是如何使用锁的内部状态，以及是如何保证线程的对共享变量的互斥修改等等这些问题，我们稍后会在锁的实现中进行介绍。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 一种锁（Ticket Lock）的实现，int ticket 和 int turn 就是锁的内部状态</span>
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token keyword">int</span> ticket<span class="token punctuation">;</span>
    <span class="token keyword">int</span> turn<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><code>lock</code>操作的含义是这样的：</p>
<blockquote>
<p>当<code>线程A</code>对某个锁<code>mutex</code>进行<code>lock</code>操作时：</p>
<ul>
<li><p><code>线程A</code>首先尝试获得锁</p>
</li>
<li><p>如果当前锁<code>mutex</code>被其他线程占用，例如<code>线程B</code>，则放弃<code>CPU</code>，让别的线程运行，等待下一次调度，然后继续尝试获得锁。PS：如果标记某个锁<code>mutex</code>是否被某个线程占用，其实直接利用锁内部的某个状态即可。例如：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    bool if_occupied<span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>此外，放弃<code>CPU</code>这个操作虽然间接的操控了调度器，不过当前现场放弃<code>CPU</code>让其他线程使用<code>CPU</code>总比当前线程一直占用<code>CPU</code>不让其他线程运行来得好。所以放弃<code>CPU</code>这种变相操控调度器的操作是被允许的。</p>
</li>
<li><p>如果当前锁<code>mutex</code>没有被其他线程占用，则当前线程占用该锁（例如将<code>if_occupied</code>变量修改为<code>true</code>），并修改全局变量。</p>
</li>
<li><p>在当前进程完成修改全局变量后，调用<code>unlock</code>释放锁。</p>
</li>
</ul>
</blockquote>
<p>而<code>unlock</code>操作就要简单很多，就是把传入的锁<code>mutex</code>中的<code>if_occupied</code>设为<code>false</code>即可。</p>
<h3 id="5-临界区（Critical-Section）"><a href="#5-临界区（Critical-Section）" class="headerlink" title="5. 临界区（Critical Section）"></a>5. 临界区（Critical Section）</h3><p>上面我们介绍完了锁，接下来介绍一下与锁相关的临界区的定义。我们回顾一下上面使用锁成功的解决共享变量问题的代码：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">thread_A</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    <span class="token function">lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    balance <span class="token operator">=</span> balance <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token function">unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>这里，会发生问题的地方就是<code>balance = balance + 1</code>，即修改共享变量的地方，<strong>一般我们将修改共享变量的代码区域称为临界区（Critical Section）</strong>。</p>
<p><strong>所以我们在多线程开发的时候，需要使用锁区保护临界区。因此未来只要是涉及到修改全局变量的地方，都是临界区，而进入临界区前上锁，即用锁来保护临界区。</strong></p>
<p><strong>而根据具体的要求的不同，进入临界区前上的锁也不同。</strong></p>
<h3 id="6-各种锁：互斥锁、条件锁（条件变量）、自旋锁、信号量"><a href="#6-各种锁：互斥锁、条件锁（条件变量）、自旋锁、信号量" class="headerlink" title="6. 各种锁：互斥锁、条件锁（条件变量）、自旋锁、信号量"></a>6. 各种锁：互斥锁、条件锁（条件变量）、自旋锁、信号量</h3><p>事实上，因为实现的方式不同，锁有很多种，例如：<code>互斥锁</code>、<code>条件锁</code>（又称为<code>条件变量</code>）、<code>自旋锁</code>等等。我们上面介绍的锁称为<code>互斥锁（Mutual Exclusion）</code>，只是诸多锁中的一种锁。</p>
<blockquote>
<p>PS：锁的实现是包括：锁的定义、<code>lock</code>操作和<code>unlock</code>操作的实现等等在内的，而不仅仅是光<code>lock</code>一个结构体的定义就结束了。</p>
</blockquote>
<p><strong>每种锁本质上都是去解决多线程编程中针对共享变量存在的问题</strong>，例如：</p>
<ul>
<li><code>互斥锁</code>想要解决的问题就是共享数据的同时修改问题，<code>互斥锁</code>本意就是让线程间互斥的修改全局变量</li>
<li><code>条件锁</code>则是针对多个线程同时操作全局容器变量时存在的问题（例如全局的队列只有一个位置了，但是两个线程同时向队列中添加元素，就会造成溢出或者写入的数据不对的情况）。因此<code>条件锁</code>的本意就是让线程在满足条件的前提下（队列有足够的空间）修改全局变量。</li>
<li>……</li>
</ul>
<p>根绝具体的共享数据时我们需要解决的问题不同，其实有很多很多的锁，甚至我们自己为了提高我们写的程序的性能，在对程序的多线程并发情况进行分析后，我们也能够设计符合我们的需求的、性能更好的锁。</p>
<p>虽然说锁有很多很多种锁，但是最基本的锁其实就只有几种，而<code>互斥锁</code>、<code>条件锁</code>、<code>自旋锁</code>又做为基础中的基础，是必须要掌握的。其他的锁根绝我们程序的需要进行修改即可。</p>
<p>因此，我们接下来就将介绍<code>互斥锁</code>、<code>条件锁</code>、<code>自旋锁</code>、<code>信号量</code>的实现以及具体适用的场景。</p>
<h3 id="7-锁的悖论"><a href="#7-锁的悖论" class="headerlink" title="7. 锁的悖论"></a>7. 锁的悖论</h3><p>我们上面介绍了锁机制，但其实锁有一个问题，我们刻意回避了，一直没有讲，即：<strong>有没有可能锁中也需要原子操作？</strong></p>
<p>PS：如果你没有认真看前面的内容，那么这里你可能会有一个疑问：如果锁中也需要原子操作的话，会不会存在一个悖论：<strong>我们使用锁来为避免原子操作，可是锁的实现却又需要原子操作</strong>。</p>
<blockquote>
<p>如果你有这个疑问，那么恭喜你，你是认真思考了，只不过文章看的不是那么认真。如果你没有这个疑问，那么你看的实在是太不认真了。</p>
</blockquote>
<p>这个疑问的来源就是下面的例子：</p>
<p>假设我们给出如下锁以及配套的<code>lock</code>和<code>unlock</code>的定义：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    bool if_occupied<span class="token punctuation">;</span>
  <span class="token keyword">int</span> waiting_thread<span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  lock<span class="token operator">-></span>if_occupied <span class="token operator">=</span> true<span class="token punctuation">;</span>
  lock<span class="token operator">-></span>waiting_thread <span class="token operator">+</span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  lock<span class="token operator">-></span>if_occupied <span class="token operator">=</span> false<span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>则由于我们在<code>lock</code>操作中还是出现了<code>lock-&gt;waiting_thread += 1</code>这样的操作，<strong>这就要求我们在锁中必须要实现<code>原子加法</code>等简单的原子操作</strong>，否则锁就不能正常工作了。可是我们却在前面的的章节说，锁机制是为了避免进行原子操作的，这不是自相矛盾了么？</p>
<p>其实没有矛盾，<strong>我们在前面说的是，并且这里需要再次强调是，<code>使用锁的本意是：避免让一些复杂的操作成为原子操作</code>，而非完全不适用原子操作，使用一些简单的原子操作，例如原子加法是必要的。所以并不是完全不适用原子操作，而是使用简单原子操作，避免复杂原子操作。</strong></p>
<p>不过，在真正的操作系统中，用的不是原子加减法，而是更加高效的<code>xchg</code>指令。因此，我们下面就讲讲简单的原子操作的实现。</p>
<h2 id="二、原子操作的实现"><a href="#二、原子操作的实现" class="headerlink" title="二、原子操作的实现"></a>二、原子操作的实现</h2><h3 id="1-错误的实现：关中断"><a href="#1-错误的实现：关中断" class="headerlink" title="1. 错误的实现：关中断"></a>1. 错误的实现：关中断</h3><p><strong>上面说到，<code>lock</code>和<code>unlock</code>中可能也需要有一些操作是原子操作。而原子操作的含义是原子操作的指令不会被中断，那么既然这样，我能不能直接关掉中断？这样就相当于变相的实现了原子操作</strong></p>
<p>例如：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    bool if_occupied<span class="token punctuation">;</span>
  <span class="token keyword">int</span> waiting_thread<span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>


<span class="token keyword">int</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  关中断<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  开中断<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>关中断的的好处是简单，但是问题却很大：</p>
<p><strong>第一个问题就是程序可能永久的运行</strong>。例如程序在开头就直接<code>lock</code>。而由于中断被关闭了，用户通过键盘输入<code>Ctrl+C</code>触发键盘输入中断来让操作系统结束掉程序，或者主板上的时钟到时间了发出时钟中断让操作系统切换新的进程等等功能都无法实现了。造成的后果就是用户的程序一直运行，即便是操作系统都没有办法运行了，此时唯一可能结束用户程序的方法就是断电重启。</p>
<p><strong>第二个问题就是，多处理器上关中断的方法无效</strong>。因为是<code>CPU</code>去响应中断的，因此我们如果只关掉一个<code>CPU</code>的中断，那么还是会有别的<code>CPU</code>去响应中断，所以还是没用，如果都关掉了，那么就成了第一个问题。</p>
<p><strong>第三个问题就是，开关中断间的时间过长会导致计算机系统会丢失一些中断</strong>。例如在这期间的键盘输入、鼠标滑动等等都是以中断的方式让计算机的值得。因为人类通过键盘输入数据（按下键盘）本身就是随机事件，面对随机事件，如果让<code>CPU</code>循环去检测随机时间是否发生（例如用户是否按下按键），那么效率是非常低的。</p>
<p>因此现代计算机都是通过中断的形式去处理随机事件的，当用户按下按键，会有专门的硬件电路通知<code>CPU</code>，按键被按下了，这个时候<code>CPU</code>就会先去处理按键，而后再运行先前的程序。而导致硬件发出信号的原因不同，因此中断源不同。</p>
<p><strong>可以说，现代计算机就是建立在中断的基础上的，关中断的这种方式来实现原子操作基本等于自杀。</strong></p>
<h3 id="2-正确的实现：额外的硬件指令"><a href="#2-正确的实现：额外的硬件指令" class="headerlink" title="2. 正确的实现：额外的硬件指令"></a>2. 正确的实现：额外的硬件指令</h3><p><strong>我们在最上面说过，每个机器指令都是有一个具体得硬件电路的实现的</strong>。而高级语言中加法出现问题的地方就在于高级语言认为的加法其实并不是一条加法指令，而是三条指令：</p>
<ul>
<li>从内存中获取变量值到寄存器中</li>
<li>对寄存器中的值进行加法</li>
<li>将寄存器中的值写入到内存中</li>
</ul>
<p>所以，为了能够实现原子操作，我们就需要设计额外的硬件指令。</p>
<p>设计新的指令之前，我们先思考一下，是什么导致高级语言的加法不是原子操作，即首先找出问题所在，而后再针对性的设计新的指令。</p>
<p>机器语言的加法最大的问题就是加法只是针对寄存器进行操作的。而寄存器中的值都是<code>易失性</code>的因此，因此，<strong>如果想要实现原子性操作，就需要有一个指令能够直接对内存进行操作</strong>。这个指令就是<code>xchg</code>指令。</p>
<p>PS：如果我们能够实现<code>memory-based add</code>的话，那么这个<code>add</code>指令其实就是原子操作，因为包含了读内存、加、写内存操作在一起。</p>
<blockquote>
<p><strong><code>xchg</code>指令是交换指令，具体功能就是将两个寄存器，或者寄存器和内存变量之间内容进行交换的指令</strong></p>
</blockquote>
<p>因此，<code>xchg</code>就是一个原子操作，具体包括了：</p>
<ul>
<li>读取内存中变量的值到寄存器B</li>
<li>互换寄存器A中的值和寄存器B中的值</li>
<li>寄存器B中的值写入内存中</li>
</ul>
<p>而通过<code>xchg</code>这个原子操作，我们就可以去构建不同的锁。</p>
<p>接下来，我们就要讲解不同的锁的实现。</p>
<h2 id="三、自旋锁（Spin-Lock）"><a href="#三、自旋锁（Spin-Lock）" class="headerlink" title="三、自旋锁（Spin Lock）"></a>三、自旋锁（Spin Lock）</h2><p>上面我们讲了<code>xchg</code>这个原子指令之后，我们接下将讲解<code>自旋锁（Spin Lock)</code>。</p>
<p><strong><code>自旋锁</code>简单的来说就是：自旋锁就是资金进不去就在门外等着，自己进去了就让别人在门外等着</strong>。作用和前面讲的互斥锁一样的，都是保证临界区唯一访问，从而解决数据不一致问题。</p>
<h3 id="1-自旋锁实现——TestAndSwap"><a href="#1-自旋锁实现——TestAndSwap" class="headerlink" title="1. 自旋锁实现——TestAndSwap"></a>1. 自旋锁实现——TestAndSwap</h3><h4 id="A-实现"><a href="#A-实现" class="headerlink" title="A. 实现"></a>A. 实现</h4><p>讲解<code>自旋锁</code>的<code>TestAndSwap</code>实现前，首先需要讲解<code>TestAndSwap</code>函数。</p>
<p><code>TestAndSwap</code>函数中调用了<code>xchg</code>指令最终是一个原子函数，<strong>而其实现的功能</strong>如下（注意，这里只是给出了C代码的解释，真实情况下并不是这样的实现）：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 注意，TestAndSet函数的调用是原子的，即下面的Atomic</span>
<span class="token keyword">int</span> <span class="token function">TestAndSet</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>old_ptr<span class="token punctuation">,</span> <span class="token keyword">int</span> new<span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">int</span> old <span class="token operator">=</span> <span class="token operator">*</span>old_ptr<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// fetch old value at old_ptr</span>
  <span class="token operator">*</span>old_ptr <span class="token operator">=</span> new<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// store ’new’ into old_ptr</span>
  <span class="token keyword">return</span> old<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// return the old value</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>即，<code>将变量设置为新的值，同时返回变量旧的值</code>。</p>
<p>自旋锁的<code>TestAndSwap</code>实现如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token keyword">int</span> flag<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>


<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 0: lock is available, 1: lock is held</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">TestAndSet</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token operator">-></span>flag<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// spin-wait (do nothing)</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>自旋锁的<code>TestAndSwap</code>实现非常简单。我们下面就将讲解自旋锁的原理。</p>
<h4 id="B-原理"><a href="#B-原理" class="headerlink" title="B. 原理"></a>B. 原理</h4><p>自旋锁的<code>TestAndSwap</code>的原理就是：</p>
<ul>
<li>假设<code>lock-&gt;flag</code>一开始等于<code>1</code>，即某个线程已经占用了锁，则<code>TestAndSet(&amp;lock-&gt;flag, 1)</code>后返回值是<code>1</code>，<code>TestAndSet(&amp;lock-&gt;flag, 1) == 1</code>成立，则当前进程循环等到锁</li>
<li>假设<code>lock-&gt;flag</code>一开始等于<code>0</code>，则当前进程获得锁，然后进入临界区修改共享变量</li>
</ul>
<h3 id="2-自旋锁实现——CompareAndSwap"><a href="#2-自旋锁实现——CompareAndSwap" class="headerlink" title="2. 自旋锁实现——CompareAndSwap"></a>2. 自旋锁实现——CompareAndSwap</h3><h4 id="A-实现-1"><a href="#A-实现-1" class="headerlink" title="A. 实现"></a>A. 实现</h4><p>自旋锁的另外一种实现方式就是使用<code>CompareAndSwap</code>函数。</p>
<p>类似于<code>TestAndSet</code>是原子函数一样，<code>CompareAndSwap</code>也是原子函数，其功能的C语言描述（非实现）如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">CompareAndSwap</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>ptr<span class="token punctuation">,</span> <span class="token keyword">int</span> expected<span class="token punctuation">,</span> <span class="token keyword">int</span> new<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">int</span> original <span class="token operator">=</span> <span class="token operator">*</span>ptr<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>original <span class="token operator">==</span> expected<span class="token punctuation">)</span>
        <span class="token operator">*</span>ptr <span class="token operator">=</span> new<span class="token punctuation">;</span>
    <span class="token keyword">return</span> original<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>所以，自旋锁的<code>CompareAndSwap</code>实现中，就只有<code>lock</code>函数发生了改变</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token keyword">int</span> flag<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>


<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 0: lock is available, 1: lock is held</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">CompareAndSwap</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token operator">-></span>flag<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// spin</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-原理-1"><a href="#B-原理-1" class="headerlink" title="B. 原理"></a>B. 原理</h4><p>自旋锁的<code>CompareAndSet</code>的原理就是：</p>
<ul>
<li>假设<code>lock-&gt;flag</code>一开始等于<code>1</code>，即某个线程已经占用了锁，则<code>CompareAndSet(&amp;lock-&gt;flag, 0, 1)</code>后返回值是<code>1</code>，<code>CompareAndSet(&amp;lock-&gt;flag, 0, 1) == 1</code>成立，则当前进程循环等到锁</li>
<li>假设<code>lock-&gt;flag</code>一开始等于<code>0</code>，则当前进程获得锁，然后进入临界区修改共享变量</li>
</ul>
<h2 id="四、互斥锁（Mutual-Exclusion）"><a href="#四、互斥锁（Mutual-Exclusion）" class="headerlink" title="四、互斥锁（Mutual Exclusion）"></a>四、互斥锁（Mutual Exclusion）</h2><p><code>互斥锁</code>的作用其实前面已经介绍过了，就是保证临界区的唯一访问，从而解决了数据不一致问题。和<code>互斥锁</code>作用一样。但是互斥锁的性能会高很多，主要就是因为使用了<code>yield</code>函数。</p>
<h3 id="1-yield函数"><a href="#1-yield函数" class="headerlink" title="1. yield函数"></a>1. yield函数</h3><p>前面的自旋锁性能比较低，原因就在于自旋锁会导致等待锁的进程会循环等待。所以为了改变自旋锁的低效，互斥锁中使用<code>yield</code>函数来提升效率。</p>
<p><code>yield</code>函数的作用就是当线程主动调用<code>yield</code>函数时，调度器会将当前线程从CPU中换下来，然后让CPU去运行新的线程。</p>
<p>所以相比于<code>yield</code>这个名字，<code>sleep</code>这个名字其实更适合。</p>
<h3 id="2-互斥锁的实现"><a href="#2-互斥锁的实现" class="headerlink" title="2. 互斥锁的实现"></a>2. 互斥锁的实现</h3><p>互斥锁的实现其实和自旋锁的实现一模一样。就只有<code>lock</code>函数发生了改变</p>
<h4 id="A-TestAndSwap实现"><a href="#A-TestAndSwap实现" class="headerlink" title="A. TestAndSwap实现"></a>A. TestAndSwap实现</h4><p>互斥锁的<code>TestAndSwap</code>实现如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token keyword">int</span> flag<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>


<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 0: lock is available, 1: lock is held</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">TestAndSet</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token operator">-></span>flag<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token function">yield</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// spin-wait (do nothing)</span>
    <span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-CompareAndSwap实现"><a href="#B-CompareAndSwap实现" class="headerlink" title="B. CompareAndSwap实现"></a>B. CompareAndSwap实现</h4><p>互斥锁的<code>CompareAndSwap</code>实现如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
    <span class="token keyword">int</span> flag<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>


<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 0: lock is available, 1: lock is held</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">lock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">CompareAndSwap</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token operator">-></span>flag<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token function">yield</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// spin</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">unlock</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="五、条件锁（Conditional-Variable）"><a href="#五、条件锁（Conditional-Variable）" class="headerlink" title="五、条件锁（Conditional Variable）"></a>五、条件锁（Conditional Variable）</h2><p>前面介绍的<code>互斥锁</code>和<code>自旋锁</code>都是用于保证临界区唯一访问的，而<strong>条件锁则是用于保证在满足条件时访问临界区</strong>。</p>
<h3 id="1-条件锁的背景：生产者——消费者问题"><a href="#1-条件锁的背景：生产者——消费者问题" class="headerlink" title="1. 条件锁的背景：生产者——消费者问题"></a>1. 条件锁的背景：生产者——消费者问题</h3><p>我们上面说到，条件锁是用于在满足条件时访问临界区。条件锁最初出现的背景，就是生产者和消费者模型。</p>
<p>为此，我们先举出下面的生产者和消费者的例子：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> max <span class="token operator">=</span> <span class="token number">5</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> loops <span class="token operator">=</span> <span class="token number">20</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> numfull <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> fillptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> useptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> buffer<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
mutex_t m<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">do_fill</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span><span class="token punctuation">{</span>
  buffer<span class="token punctuation">[</span>fillptr<span class="token punctuation">]</span> <span class="token operator">=</span> value<span class="token punctuation">;</span>
  fillptrt <span class="token operator">=</span> <span class="token punctuation">(</span>fillptr <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> max<span class="token punctuation">;</span>
  numfull<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">int</span> temp <span class="token operator">=</span> buffer<span class="token punctuation">[</span>useptr<span class="token punctuation">]</span><span class="token punctuation">;</span>
  useptr <span class="token operator">=</span> <span class="token punctuation">(</span>useptr <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> max<span class="token punctuation">;</span>
  numfull<span class="token operator">--</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">producer</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> loops<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
       <span class="token comment" spellcheck="true">// do_fill中修改了共享的变量，例如buffer,fillptr,numfull等等</span>
    <span class="token comment" spellcheck="true">// 所以do_fill是临界区，需要上锁保护</span>
    <span class="token function">mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">do_fill</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">consumer</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> loops<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// do_get中修改了共享的变量，例如buffer,useptr,numfull等等</span>
    <span class="token comment" spellcheck="true">// 所以do_get是临界区，需要上锁保护</span>
    <span class="token function">mutex_loc</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> value <span class="token operator">=</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">void</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  pthread_t pid<span class="token punctuation">,</span> cid<span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 创建一个producer</span>
  <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>pid<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> producer<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 创建多个consumer</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> max<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> consumer<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token comment" spellcheck="true">// 等待线程结束运行</span>
  <span class="token function">pthread_join</span><span class="token punctuation">(</span>pid<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> max<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">pthread_join</span><span class="token punctuation">(</span>cid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>上面的例子中，生产者生产产品（一个<code>int</code>，并将产品放到仓库（<code>buffer</code>）中，而消费者从仓库中获取一个产品，而后用于后续处理。</p>
<h3 id="2-共享数据问题：数据溢出"><a href="#2-共享数据问题：数据溢出" class="headerlink" title="2. 共享数据问题：数据溢出"></a>2. 共享数据问题：数据溢出</h3><p><strong>虽然说我们上面使用了锁来保护了临界区，避免了对同时修改共享数据导致的不一致问题</strong>。</p>
<p>可是虽然避免了不一致问题事实上，上述代码中存在严重的<code>bug</code>：</p>
<ul>
<li><strong>若生产者只生产了一个产品，而后第一个消费者在获取到了该产品之后，另一个消费者继续获取产品，则此时已经没有产品可以获取。</strong></li>
<li><strong>若生产者生产了五个产品，只有一个生产者获取了一个产品后，生产者继续生产了两个产品，则此时已经已经没有地方可以继续存储产品</strong></li>
</ul>
<p>虽然我们上面的代码中，使用了<code>useptr = (userptr + 1) % max</code>和<code>fillptr = (fillptr + 1) % max</code>来避免溢出，但是会出现获取到错误的产品和覆盖未使用的产品。</p>
<p><strong>最后，导致该问题发生的根本，依旧是因为共享数据问题。而与自旋锁、互斥锁所解决的共享数据问题是数据不一致问题，而这里，我们遇到了共享数据问题中全新的一类问题：数据溢出问题</strong></p>
<h3 id="3-解决办法：条件锁"><a href="#3-解决办法：条件锁" class="headerlink" title="3. 解决办法：条件锁"></a>3. 解决办法：条件锁</h3><h4 id="A-条件锁的实现"><a href="#A-条件锁的实现" class="headerlink" title="A. 条件锁的实现"></a>A. 条件锁的实现</h4><p>为了解决数据溢出问题，我们就有了条件锁。条件锁的定义以及初始化函数如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __cond_t <span class="token punctuation">{</span>
  <span class="token keyword">int</span> flag<span class="token punctuation">;</span>
  <span class="token keyword">int</span> guard<span class="token punctuation">;</span>
  queue_t <span class="token operator">*</span>q<span class="token punctuation">;</span>
<span class="token punctuation">}</span> cond_t<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">cond_init</span><span class="token punctuation">(</span>cond_t <span class="token operator">*</span>cond<span class="token punctuation">)</span><span class="token punctuation">{</span>
  cond<span class="token operator">-></span>flag <span class="token operator">=</span> cond<span class="token operator">-></span>guard <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  cond<span class="token operator">-></span>q <span class="token operator">=</span> <span class="token function">queue_init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>条件锁中有有一个队列，这个队列是在后面针对条件锁的操作中使用到的。此外，条件锁的英文是<code>Conditional Variable</code>，因此一般缩写直接用的是<code>cond</code></p>
<p>自旋锁和互斥锁有<code>lock</code>和<code>unlock</code>两种操作，对应的，条件锁也有两种操作，只不过这两种操作称为<code>wait</code>和<code>signal</code>。</p>
<p>这两种操作的实现如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 实现代码</span>

<span class="token keyword">void</span> <span class="token function">wait</span><span class="token punctuation">(</span>cond_t <span class="token operator">*</span>cond<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token function">xchg</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token operator">-></span>guard<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">;</span>  <span class="token comment" spellcheck="true">// spin</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>cond<span class="token operator">-></span>flag <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>  <span class="token comment" spellcheck="true">// lock is free, grab it!</span>
    cond<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    cond<span class="token operator">-></span>guard <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>  <span class="token comment" spellcheck="true">// lock not free, sleep!</span>
    <span class="token function">queue_push</span><span class="token punctuation">(</span>cond<span class="token operator">-></span>q<span class="token punctuation">,</span> <span class="token function">gettid</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cond<span class="token operator">-></span>guard <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">park</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>    <span class="token comment" spellcheck="true">// put caller to sleep</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">signal</span><span class="token punctuation">(</span>cond_t <span class="token operator">*</span>cond<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">xchg</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token operator">-></span>guard<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// spin</span>
  <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">queue_empty</span><span class="token punctuation">(</span>cond<span class="token operator">-></span>q<span class="token punctuation">)</span><span class="token punctuation">)</span>
        lock<span class="token operator">-></span>flag <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token keyword">else</span>
        <span class="token function">unpark</span><span class="token punctuation">(</span><span class="token function">queue_pop</span><span class="token punctuation">(</span>cond<span class="token operator">-></span>q<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  lock<span class="token operator">-></span>guard <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>其中：</p>
<ul>
<li><p><code>park</code>和<code>unpark</code>操作是操作系统提供的函数</p>
<ul>
<li><code>park</code>的作用就是让调用的线程进入睡眠状态</li>
<li><code>unpark</code>的作用就是唤醒指定的线程<code>tid</code></li>
</ul>
</li>
<li><p><code>cond-&gt;queue</code>保存了所有睡眠线程</p>
</li>
<li><p><strong><code>guard</code>相当于条件锁<code>cond</code>自身的自旋锁，因为<code>wait</code>和<code>signal</code>中都修改了共享变量<code>cond-&gt;flag</code>和<code>cond-queue</code>，因此锁内部还需要一个自旋锁来保护<code>cond-&gt;flag</code>和<code>cond-&gt;queue</code>这两个共享的变量</strong></p>
</li>
<li><p><code>flag</code>是条件锁<code>cond</code>的内部状态，而<code>cond</code>条件锁本身用于保护外部的临界区，例如</p>
<pre class="line-numbers language-c"><code class="language-c">cond_t c<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">thread_A</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// critical section</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token function">signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>c<span class="token punctuation">)</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</li>
</ul>
<p>因此，条件锁的两种操作的含义就是：</p>
<ul>
<li><code>wait</code>操作：<ul>
<li>如果有别的线程正在操作条件锁<code>cond</code>，则循环等待（实现代码<code>4-5</code>行）。</li>
<li>获得自旋锁<code>cond-&gt;guard</code>后，首先尝试获得条件锁<code>cond</code>，如果能够获得锁（实现代码<code>6-8</code>行），那么占用锁，而后释放自旋锁</li>
<li>如果无法获得条件锁<code>cond</code>（实现代码<code>9-12</code>行），那么首先将当前线程放入睡眠线程队列中，而后释放自旋锁，而后让当前调用的进程睡眠，运行其他程序</li>
</ul>
</li>
<li><code>signal</code>操作：<ul>
<li>如果有别的线程正在操作条件锁<code>cond</code>，则循环等待（实现代码<code>17-18</code>行）。</li>
<li>获得自旋锁<code>cond-&gt;guard</code>后，若睡眠线程队列中没有正在睡眠的线程，则直接释放锁即可。</li>
<li>若睡眠线程队列中有正在睡眠的线程，则唤醒队列中的一个线程，而后释放锁。</li>
</ul>
</li>
</ul>
<h4 id="B-条件锁解决数据溢出问题"><a href="#B-条件锁解决数据溢出问题" class="headerlink" title="B. 条件锁解决数据溢出问题"></a>B. 条件锁解决数据溢出问题</h4><p>到这里，我们只是明白了条件锁的工作机制，但是还并不明白条件锁将如何帮助我们解决生产者——消费者中的数据溢出问题。下面我们就将讲解如何使用条件锁来解决数据溢出问题。</p>
<p>加上条件锁后，<code>consumer</code>和<code>producer</code>就成了下面这样：</p>
<pre class="line-numbers language-c"><code class="language-c">cond_t c<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">producer</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> loops<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
       <span class="token comment" spellcheck="true">// do_fill中修改了共享的变量，例如buffer,fillptr,numfull等等</span>
    <span class="token comment" spellcheck="true">// 所以do_fill是临界区，需要上锁保护</span>
    <span class="token function">mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 条件锁：wait操作</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>numfull <span class="token operator">==</span> max<span class="token punctuation">)</span>
      <span class="token function">cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">do_fill</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 条件锁：signal操作</span>
    <span class="token function">cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">consumer</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> loops<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// do_get中修改了共享的变量，例如buffer,useptr,numfull等等</span>
    <span class="token comment" spellcheck="true">// 所以do_get是临界区，需要上锁保护</span>
    <span class="token function">mutex_loc</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 条件锁：wait操作</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>numfull <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
          <span class="token function">cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> value <span class="token operator">=</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 条件锁：signal操作</span>
    <span class="token function">cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>上述程序中：</p>
<ul>
<li><code>producer</code>首先检查缓冲区是否满了，如果满了，则调用<code>wait</code>操作，将当前进程陷入睡眠，而后等待<code>consumer</code>消耗掉产品。</li>
<li><code>consumer</code>首先检查缓冲区是否空了，如果空了，则调用<code>wait</code>操作，将当前进程陷入睡眠，而后等待<code>producer</code>生产产品。</li>
</ul>
<p>所以：</p>
<ul>
<li>假设缓冲区为满，此时<code>producer</code>正在运行，则<code>producer</code>陷入睡眠，而后<code>consumer</code>运行，缓冲区有新的位置，<code>consumer</code>运行完毕后，调用<code>signal</code>操作，唤醒<code>producer</code>继续运行</li>
<li>假设缓冲区为空，此时<code>consumer</code>正在运行，则<code>consumer</code>陷入睡眠，而后<code>producer</code>运行，缓冲区有新的产品，<code>producer</code>运行完毕后，调用<code>signal</code>操作，唤醒<code>consumer</code>继续运行</li>
</ul>
<p>因此，通过条件锁，我们最终解决了共享拜年了中的数据溢出问题。</p>
<p><strong>而条件锁之所以称为条件锁，就是因为条件锁保证了只有在满足条件（缓冲区为空/不为空）的前提下，程序（<code>producer</code>/<code>consumer</code>）才会继续运行（想缓冲区添加产品/从缓冲区获取产品），从而避免了数据溢出问题</strong></p>
<h3 id="4-条件锁释放互斥锁"><a href="#4-条件锁释放互斥锁" class="headerlink" title="4. 条件锁释放互斥锁"></a>4. 条件锁释放互斥锁</h3><p>我们上面有一个地方没讲到，就是我们互斥锁实现的时候是</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token function">mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment" spellcheck="true">// 条件锁：wait操作</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>numfull <span class="token operator">==</span> max<span class="token punctuation">)</span>
  <span class="token function">cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">do_fill</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment" spellcheck="true">// 条件锁：signal操作</span>
<span class="token function">cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><code>cond_signal(&amp;cond)</code>操作还好理解，毕竟是针对条件锁的操作。但是为什么<code>cond_wait(&amp;cond, &amp;m)</code>还需要接受互斥锁作为参数？</p>
<p>事实上，<code>producer</code>是先获得互斥锁<code>m</code>，然后再去尝试获得条件锁<code>cond</code>的，而在获取条件锁<code>cond</code>的时候，如果直接<code>sleep</code>了，那么互斥锁就一直被<code>producer</code>占用了，而互斥锁保证了临界区只能由一个线程访问，因此即便是让<code>producer</code>睡眠了，<code>consumer</code>也没有办法运行。</p>
<p>因此，我们必须在<code>cond_wait</code>导致线程<code>sleep</code>前释放互斥锁。这就是为什么我们需要把互斥锁传入到<code>cond_wait</code>中去。而关于具体的线程<code>sleep</code>前如何释放互斥锁、线程被唤醒后如何重新获得互斥锁就不是我们所关心的了，由线程库的实现来负责。</p>
<h2 id="六、信号量（Semaphore）"><a href="#六、信号量（Semaphore）" class="headerlink" title="六、信号量（Semaphore）"></a>六、信号量（Semaphore）</h2><p>我们上面讲解了两大类不同的锁，一类是用于共享变量同步的自旋锁、互斥锁，还有一类是用于解决共享变量溢出的条件锁。而如果将两者结合起来，我们就得到了信号量，即信号量 = 互斥锁 + 条件锁。</p>
<p>接下来我们将讲解信号量。</p>
<h3 id="1-信号量定义及操作"><a href="#1-信号量定义及操作" class="headerlink" title="1. 信号量定义及操作"></a>1. 信号量定义及操作</h3><p>锁都有上锁（<code>lock</code>）和解锁（<code>unlock</code>）两种操作，虽然不同的锁可能对这两种操作的名字不一样，例如条件锁将这两个操作称为<code>wait</code>和<code>signal</code></p>
<p>信号量中将这两个操作称为<code>wait</code>和<code>post</code>，有时候也称为<code>P</code>和<code>V</code>。<code>P</code>和<code>V</code>的来就是发明信号量的是计算机届的神仙<code>Dijkstra</code>，迪杰斯特拉是荷兰人，所以<code>P</code>和<code>V</code>其实就是荷兰语中的两个单词的首字母。</p>
<p>信号量的定义、初始化操作以及<code>wait</code>和<code>post</code>操作的定义如下：</p>
<p><strong>注意，我们这里只是给出了最核心的概念，具体得实现比较复杂</strong></p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __sem_t <span class="token punctuation">{</span>
  <span class="token keyword">int</span> value<span class="token punctuation">;</span>
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span> sem_t<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">sem_init</span><span class="token punctuation">(</span>sem_t <span class="token operator">*</span>s， <span class="token keyword">int</span> value<span class="token punctuation">)</span><span class="token punctuation">{</span>
  s<span class="token operator">-></span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">sem_wait</span><span class="token punctuation">(</span>sem_t <span class="token operator">*</span>s<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token comment" spellcheck="true">// decrease value of sem_t *s by one</span>
  <span class="token comment" spellcheck="true">// wait if value of sem_t *s is negative</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">sem_post</span><span class="token punctuation">(</span>sem_t <span class="token operator">*</span>s<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token comment" spellcheck="true">// increase value of sem_t *s by one</span>
  <span class="token comment" spellcheck="true">// if 1 or more threads are waiting, wake one</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>我们能够看到，信号量和前面的自旋锁、互斥锁、条件锁最大的不同之处就在于，我们在初始化信号量的时候，可以指定其内部的初始值。而正是因为我们可以指定其初值，信号量可以实现互斥锁和条件锁的功能。</p>
<h3 id="2-信号量实现互斥"><a href="#2-信号量实现互斥" class="headerlink" title="2. 信号量实现互斥"></a>2. 信号量实现互斥</h3><p>如果将信号量的初值设为<code>1</code>，那么此时信号量就可以用于实现互斥访问。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> counter <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
sem_t lock<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token comment" spellcheck="true">// 获得锁</span>
  <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">1e6</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    counter<span class="token operator">++</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 释放锁</span>
  <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">void</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  pthread_t pid<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 初始化value为1，表示只有一个资源</span>
  <span class="token function">sem_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">5</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>pid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> worker<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 等待线程结束</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">5</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token function">pthread_join</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>pid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

  <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"counter = %d\n"</span><span class="token punctuation">,</span> counter<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="3-信号量实现Fork-Join"><a href="#3-信号量实现Fork-Join" class="headerlink" title="3. 信号量实现Fork/Join"></a>3. 信号量实现Fork/Join</h3><p>信号量还可以实现保证在子线程运行特定行代码后再运行主线程/其他线程</p>
<pre class="line-numbers language-c"><code class="language-c">sem_t s<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">child</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"child\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 将子线程是否运行到这里视为一个资源，运行到这里表示有一个资源了</span>
  <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  pthread_t p<span class="token punctuation">;</span>
  <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"parent: begin\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 将子线程是否运行到特定行视为一个资源，一开始没有运行到，所以没有资源</span>
  <span class="token function">sem_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>s<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>p<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> child<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment" spellcheck="true">// 等待子线程放入资源</span>
  <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="4-信号量实现读者写者锁"><a href="#4-信号量实现读者写者锁" class="headerlink" title="4. 信号量实现读者写者锁"></a>4. 信号量实现读者写者锁</h3><p>读者写者锁允许多个读者线程访问（只读）共享资源，而只允许一个写者访问（修改）共享资源</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> struc __rwlock_t <span class="token punctuation">{</span>
  sem_t write_lock<span class="token punctuation">;</span>
  sem_t lock<span class="token punctuation">;</span>
  <span class="token keyword">int</span> readers<span class="token punctuation">;</span>
<span class="token punctuation">}</span> rwlock_t<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">rw_init</span><span class="token punctuation">(</span>rwlock_t <span class="token operator">*</span>L<span class="token punctuation">)</span><span class="token punctuation">{</span>
  L<span class="token operator">-></span>readers <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token function">sem_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>lock<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">sem_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>write_lock<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">acquire_readlock</span><span class="token punctuation">(</span>rwlock_t <span class="token operator">*</span>L<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
  L<span class="token operator">-></span>readers<span class="token operator">++</span><span class="token punctuation">;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>L<span class="token operator">-></span>readers <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>write_lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">release_readlock</span><span class="token punctuation">(</span>rwlock_t <span class="token operator">*</span>L<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
  L<span class="token operator">-></span>reader<span class="token operator">--</span><span class="token punctuation">;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>L<span class="token operator">-></span>reader <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>write_lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">acquire_writelock</span><span class="token punctuation">(</span>rwlock_t <span class="token operator">*</span>L<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">sem_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>write_lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">release_writelock</span><span class="token punctuation">(</span>rwlock_t <span class="token operator">*</span>L<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token function">sem_post</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>L<span class="token operator">-></span>write_lock<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="七、Ticket-Lock"><a href="#七、Ticket-Lock" class="headerlink" title="七、Ticket Lock"></a>七、Ticket Lock</h2><p>我们前面讲了各种不同的锁，我们接下来给出一个自定义的锁<code>Ticket Lock</code>的视线</p>
<h3 id="1-FetchAndAdd操作"><a href="#1-FetchAndAdd操作" class="headerlink" title="1. FetchAndAdd操作"></a>1. FetchAndAdd操作</h3><p>我们接下来给出一个新的原子函数，下面只是解释，而不是真实的实现：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">FetchAndAdd</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>ptr<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">int</span> old <span class="token operator">=</span> <span class="token operator">*</span>ptr<span class="token punctuation">;</span>
    <span class="token operator">*</span>ptr <span class="token operator">=</span> old <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> old<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="2-Ticket-Lock实现"><a href="#2-Ticket-Lock实现" class="headerlink" title="2. Ticket Lock实现"></a>2. Ticket Lock实现</h3><p>我们这里通过<code>FetchAndAdd</code>实现<code>Ticket Lock</code>。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> __lock_t <span class="token punctuation">{</span>
  <span class="token keyword">int</span> ticket<span class="token punctuation">;</span>
  <span class="token keyword">int</span> turn<span class="token punctuation">;</span>
<span class="token punctuation">}</span> lock_t<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">lock_init</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  lock<span class="token operator">-></span>ticket <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  lock<span class="token operator">-></span>turn <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">acquire</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">int</span> myturn <span class="token operator">=</span> <span class="token function">FetchAndAdd</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>lock<span class="token operator">-></span>ticket<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">while</span> <span class="token punctuation">(</span>lock<span class="token operator">-></span>turn <span class="token operator">!=</span> myturn<span class="token punctuation">)</span>
    <span class="token punctuation">;</span>  <span class="token comment" spellcheck="true">// spin</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">release</span><span class="token punctuation">(</span>lock_t <span class="token operator">*</span>lock<span class="token punctuation">)</span><span class="token punctuation">{</span>
  lock<span class="token operator">-></span>turn <span class="token operator">+</span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/about" rel="external nofollow noreferrer">Jack Wang</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://jackwang0107.github.io/2022/11/13/suo-ji-qi-shi-xian-hu-chi-suo-tiao-jian-bian-liang-yi-ji-xin-hao-liang/">https://jackwang0107.github.io/2022/11/13/suo-ji-qi-shi-xian-hu-chi-suo-tiao-jian-bian-liang-yi-ji-xin-hao-liang/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/about" target="_blank">Jack Wang</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/tags/Operating-System/">
                                    <span class="chip bg-color">Operating System</span>
                                </a>
                            
                                <a href="/tags/%E9%94%81/">
                                    <span class="chip bg-color">锁</span>
                                </a>
                            
                                <a href="/tags/%E4%BF%A1%E5%8F%B7%E9%87%8F/">
                                    <span class="chip bg-color">信号量</span>
                                </a>
                            
                                <a href="/tags/%E4%BA%92%E6%96%A5%E9%94%81/">
                                    <span class="chip bg-color">互斥锁</span>
                                </a>
                            
                                <a href="/tags/%E8%87%AA%E6%97%8B%E9%94%81/">
                                    <span class="chip bg-color">自旋锁</span>
                                </a>
                            
                                <a href="/tags/%E6%9D%A1%E4%BB%B6%E9%94%81/">
                                    <span class="chip bg-color">条件锁</span>
                                </a>
                            
                                <a href="/tags/%E6%9D%A1%E4%BB%B6%E5%8F%98%E9%87%8F/">
                                    <span class="chip bg-color">条件变量</span>
                                </a>
                            
                                <a href="/tags/%E9%94%81%E7%9A%84%E5%AE%9E%E7%8E%B0/">
                                    <span class="chip bg-color">锁的实现</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/medias/reward/alipay.png" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/medias/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/2022/11/15/cao-zuo-xi-tong-fang-wen-nei-cun/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221117233832116.png" class="responsive-img" alt="CPU访问内存：内存分段与内存分页">
                        
                        <span class="card-title">CPU访问内存：内存分段与内存分页</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文介绍了CPU访问内存的两种方式：内存分段式访问与内存分页式访问。此外还讲解了包括物理地址、逻辑地址、有效地址和虚拟地址等等在内的概念
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2022-11-15
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                    操作系统
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/%E7%89%A9%E7%90%86%E5%9C%B0%E5%9D%80/">
                        <span class="chip bg-color">物理地址</span>
                    </a>
                    
                    <a href="/tags/%E9%80%BB%E8%BE%91%E5%9C%B0%E5%9D%80/">
                        <span class="chip bg-color">逻辑地址</span>
                    </a>
                    
                    <a href="/tags/%E6%9C%89%E6%95%88%E5%9C%B0%E5%9D%80/">
                        <span class="chip bg-color">有效地址</span>
                    </a>
                    
                    <a href="/tags/%E7%BA%BF%E6%80%A7%E5%9C%B0%E5%9D%80/">
                        <span class="chip bg-color">线性地址</span>
                    </a>
                    
                    <a href="/tags/%E8%99%9A%E6%8B%9F%E5%9C%B0%E5%9D%80/">
                        <span class="chip bg-color">虚拟地址</span>
                    </a>
                    
                    <a href="/tags/%E5%AE%9E%E6%A8%A1%E5%BC%8F/">
                        <span class="chip bg-color">实模式</span>
                    </a>
                    
                    <a href="/tags/%E4%BF%9D%E6%8A%A4%E6%A8%A1%E5%BC%8F/">
                        <span class="chip bg-color">保护模式</span>
                    </a>
                    
                    <a href="/tags/%E6%AE%B5%E9%80%89%E6%8B%A9%E5%AD%90/">
                        <span class="chip bg-color">段选择子</span>
                    </a>
                    
                    <a href="/tags/%E6%AE%B5%E6%8F%8F%E8%BF%B0%E7%AC%A6%E8%A1%A8/">
                        <span class="chip bg-color">段描述符表</span>
                    </a>
                    
                    <a href="/tags/%E7%9F%AD%E6%8F%8F%E8%BF%B0%E7%AC%A6/">
                        <span class="chip bg-color">短描述符</span>
                    </a>
                    
                    <a href="/tags/%E5%86%85%E5%AD%98%E5%88%86%E6%AE%B5/">
                        <span class="chip bg-color">内存分段</span>
                    </a>
                    
                    <a href="/tags/%E5%86%85%E5%AD%98%E5%88%86%E9%A1%B5/">
                        <span class="chip bg-color">内存分页</span>
                    </a>
                    
                    <a href="/tags/%E9%A1%B5%E8%A1%A8/">
                        <span class="chip bg-color">页表</span>
                    </a>
                    
                    <a href="/tags/%E9%A1%B5%E8%A1%A8%E9%A1%B9/">
                        <span class="chip bg-color">页表项</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/2022/11/10/linux-san-jian-ke-grep-sed-he-awk/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/1920px-Maurice_Leloir_-_Le_ballet_de_la_Merlaison-20221112005700739.jpg" class="responsive-img" alt="Linux三剑客">
                        
                        <span class="card-title">Linux三剑客</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文主要介绍了Linux三剑客：grep、sed和awk
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2022-11-10
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Linux%E5%AE%9E%E7%94%A8%E6%8A%80%E5%B7%A7/" class="post-category">
                                    Linux实用技巧
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Linux/">
                        <span class="chip bg-color">Linux</span>
                    </a>
                    
                    <a href="/tags/Ubuntu/">
                        <span class="chip bg-color">Ubuntu</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE' || selection.getRangeAt(0).commonAncestorContainer.nodeName === 'CODE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: JackWang&#39;s Blog<br />'
            + '文章作者: Jack Wang<br />'
            + '文章链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () {bodyElement.removeChild(newdiv);}, 200);
    });
</script>


<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('2'),
            headingSelector: 'h1, h2, h3, h4, h5, h6'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4, h5, h6').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




    <footer class="page-footer bg-color">
    

    <div class="container row center-align"
         style="margin-bottom: 15px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2021-2023</span>
            
            <a href="/about" target="_blank">Jack Wang</a>
            <!-- |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a> -->
            <!-- |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a> -->
            <br>
            
                &nbsp;<i class="fas fa-chart-area"></i>&nbsp;站点总字数:&nbsp;<span
                        class="white-color">603.8k</span>
            
            
            
                
            
            
                <span id="busuanzi_container_site_pv">
                &nbsp;|&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;
                    <span id="busuanzi_value_site_pv" class="white-color"></span>
            </span>
            
            
                <span id="busuanzi_container_site_uv">
                &nbsp;|&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;
                    <span id="busuanzi_value_site_uv" class="white-color"></span>
            </span>
            
            <br>

            <!-- 运行天数提醒. -->
            
                <span id="sitetime"> Loading ...</span>
                <script>
                    var calcSiteTime = function () {
                        var seconds = 1000;
                        var minutes = seconds * 60;
                        var hours = minutes * 60;
                        var days = hours * 24;
                        var years = days * 365;
                        var today = new Date();
                        var startYear = "2021";
                        var startMonth = "11";
                        var startDate = "12";
                        var startHour = "0";
                        var startMinute = "0";
                        var startSecond = "0";
                        var todayYear = today.getFullYear();
                        var todayMonth = today.getMonth() + 1;
                        var todayDate = today.getDate();
                        var todayHour = today.getHours();
                        var todayMinute = today.getMinutes();
                        var todaySecond = today.getSeconds();
                        var t1 = Date.UTC(startYear, startMonth, startDate, startHour, startMinute, startSecond);
                        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
                        var diff = t2 - t1;
                        var diffYears = Math.floor(diff / years);
                        var diffDays = Math.floor((diff / days) - diffYears * 365);

                        // 区分是否有年份.
                        var language = 'zh-CN';
                        if (startYear === String(todayYear)) {
                            document.getElementById("year").innerHTML = todayYear;
                            var daysTip = 'This site has been running for ' + diffDays + ' days';
                            if (language === 'zh-CN') {
                                daysTip = '本站已运行 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                daysTip = '本站已運行 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = daysTip;
                        } else {
                            document.getElementById("year").innerHTML = startYear + " - " + todayYear;
                            var yearsAndDaysTip = 'This site has been running for ' + diffYears + ' years and '
                                + diffDays + ' days';
                            if (language === 'zh-CN') {
                                yearsAndDaysTip = '本站已运行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                yearsAndDaysTip = '本站已運行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = yearsAndDaysTip;
                        }
                    }

                    calcSiteTime();
                </script>
            
            <br>
            
                <span id="icp"><img src="/medias/icp.png"
                                    style="vertical-align: text-bottom;"/>
                <a href="https://beian.miit.gov.cn" target="_blank">陕ICP备2021014294号-1</a>
            </span>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/jackwang0108" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2232123545@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2232123545" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2232123545" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    

    
        
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="/libs/others/sakura.js"><\/script>');
            }
        </script>
    

    <!-- 雪花特效 -->
    

    <!-- 鼠标星星特效 -->
    

     
        <script src="https://ssl.captcha.qq.com/TCaptcha.js"></script>
        <script src="/libs/others/TencentCaptcha.js"></script>
        <button id="TencentCaptcha" data-appid="xxxxxxxxxx" data-cbfn="callback" type="button" hidden></button>
    

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    <script src="/libs/others/clicklove.js" async="async"></script>
    
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    

    

    

    <!--腾讯兔小巢-->
    
    

    

    

    
    <script src="/libs/instantpage/instantpage.js" type="module"></script>
    

</body>

</html>
